﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Percolation
{
    [Serializable]
    sealed class HKResultNet: NetInterface
    {
        public int[,] Net { get; private set; }
        private int m_width;
        private int m_height;

        public HKResultNet(int width, int height)
        {
            m_width = width;
            m_height = height;
            Net = new int[m_width, m_height];
        }

        public int getWidth()
        {
            return m_width;
        }

        public int getHeight()
        {
            return m_height;
        }

        public int getValue(int x, int y)
        {
            if (x < 0 || x >= m_width)
                throw new IndexOutOfRangeException("Percolation.NetGenerator.NetBase.getValue(int x, int y) - error in 'x' parameter");
            if (y < 0 || y >= m_height)
                throw new IndexOutOfRangeException("Percolation.NetGenerator.NetBase.getValue(int x, int y) - error in 'y' parameter");

            return Net[x, y];
        }
    }

    [Serializable]
    public class HKStatistics
    {
        public NetInterface ResultNet { get; private set; }
        public int ClusterCount { get; private set; }
        public double ClusterAvgSize { get; private set; }
        public int ClusterMaxSize { get; private set; }
        public int ClusterMinSize { get; private set; }
        public bool Percolation { get; private set; }
        public int PercolationClusterSize { get; private set; }

        private bool isPercolationCluster(List<HoshenKopelmanNumbering.Point> clusterPoints, int startY, int endY)
        {
            bool startFound = false, endFound = false;
            foreach (HoshenKopelmanNumbering.Point p in clusterPoints)
            {
                if (!startFound && p.Y == startY)
                    startFound = true;

                if (!endFound && p.Y == endY)
                    endFound = true;
            }

            return startFound && endFound;
        }

        public HKStatistics(NetInterface resultNet, SortedDictionary<int, List<HoshenKopelmanNumbering.Point>> clusterDict)
        {
            ResultNet = resultNet;

            ClusterCount = clusterDict.Count;
            ClusterMaxSize = Int32.MinValue;
            ClusterMinSize = Int32.MaxValue;
            ClusterAvgSize = 0;
            PercolationClusterSize = 0;
            Percolation = false;

            foreach (var p in clusterDict)
            {
                int points = p.Value.Count;
                ClusterAvgSize += points;

                if (points > ClusterMaxSize)
                    ClusterMaxSize = points;
                if (points < ClusterMinSize)
                    ClusterMinSize = points;

                if (!Percolation)
                {
                    Percolation = isPercolationCluster(p.Value, ResultNet.getHeight(), 1);
                    if (Percolation)
                        PercolationClusterSize = p.Value.Count;
                }
            }

            ClusterAvgSize /= ClusterCount;
        }
    }

    public static class HoshenKopelmanNumbering
    {
        private struct Cell
        {
            public int Color { get; set; }
            public int ClusterNum { get; set; } 
        }

        public struct Point
        {
            public int X { get; set; }
            public int Y { get; set; }
        }

        public static HKStatistics numberate(NetInterface net)
        {
            Cell[,] tempNet = new Cell[net.getWidth() + 1, net.getHeight() + 1];

            for (int i = 0; i < net.getWidth() + 1; ++i)
            {
                for (int j = 0; j < net.getHeight() + 1; ++j)
                {
                    if (i == 0 || j == 0)
                        tempNet[i, j].Color = NetCellColor.White;
                    else
                        tempNet[i, j].Color = net.getValue(i - 1, j - 1);
                    
                    tempNet[i, j].ClusterNum = 0;
                }
            }

            SortedDictionary<int, List<Point>> dict = new SortedDictionary<int, List<Point>>();
            for (int j = 1; j < net.getHeight() + 1; ++j)
            {
                for (int i = 1; i < net.getWidth() + 1; ++i)
                {
                    if (tempNet[i, j].Color == NetCellColor.White)
                        continue;

                    int leftCellColor = tempNet[i - 1, j].Color;
                    int topCellColor = tempNet[i, j - 1].Color;

                    if (leftCellColor == NetCellColor.White && topCellColor == NetCellColor.White)
                    {
                        List<Point> clusterList = new List<Point>();
                        Point pnt = new Point { X = i, Y = j };
                        clusterList.Add(pnt);

                        dict.Add((dict.Keys.Count == 0) ? 1 : dict.Keys.Max() + 1, clusterList);
                        tempNet[i, j].ClusterNum = dict.Keys.Max();
                    }
                    else if (leftCellColor == NetCellColor.Black && topCellColor == NetCellColor.White)
                    {
                        Point pnt = new Point { X = i, Y = j };
                        dict[tempNet[i - 1, j].ClusterNum].Add(pnt);
                        tempNet[i, j].ClusterNum = tempNet[i - 1, j].ClusterNum;
                    }
                    else if (leftCellColor == NetCellColor.White && topCellColor == NetCellColor.Black)
                    {
                        Point pnt = new Point { X = i, Y = j };
                        dict[tempNet[i, j - 1].ClusterNum].Add(pnt);
                        tempNet[i, j].ClusterNum = tempNet[i, j - 1].ClusterNum;
                    }
                    else if (leftCellColor == NetCellColor.Black && topCellColor == NetCellColor.Black)
                    {
                        int leftCellCluster = tempNet[i - 1, j].ClusterNum;
                        int topCellCluster = tempNet[i, j - 1].ClusterNum;

                        if (leftCellCluster < topCellCluster)
                        {
                            foreach (Point p in dict[topCellCluster])
                            {
                                dict[leftCellCluster].Add(p);
                                tempNet[p.X, p.Y].ClusterNum = leftCellCluster;
                            }

                            Point pnt = new Point { X = i, Y = j };

                            dict[leftCellCluster].Add(pnt);
                            tempNet[i, j].ClusterNum = leftCellCluster;

                            if (topCellCluster != dict.Keys.Last())
                            {
                                int l = topCellCluster;
                                while (l < dict.Count)
                                {
                                    dict.Remove(l);
                                    foreach (Point p in dict[l + 1])
                                        tempNet[p.X, p.Y].ClusterNum = l;

                                    dict.Add(l, dict[l + 1]);
                                    ++l;
                                }
                            }

                            dict.Remove(dict.Count);
                        }
                        else if (leftCellCluster > topCellCluster)
                        {
                            foreach (Point p in dict[leftCellCluster])
                            {
                                dict[topCellCluster].Add(p);
                                tempNet[p.X, p.Y].ClusterNum = topCellCluster;
                            }

                            Point pnt = new Point { X = i, Y = j };

                            dict[topCellCluster].Add(pnt);
                            tempNet[i, j].ClusterNum = topCellCluster;

                            if (leftCellCluster != dict.Keys.Last())
                            {
                                int l = leftCellCluster;
                                while (l < dict.Count)
                                {
                                    dict.Remove(l);
                                    foreach (Point p in dict[l + 1])
                                        tempNet[p.X, p.Y].ClusterNum = l;

                                    dict.Add(l, dict[l + 1]);
                                    ++l;
                                }
                            }

                            dict.Remove(dict.Count);
                        }
                        else
                        {
                            Point pnt = new Point { X = i, Y = j };
                            dict[leftCellCluster].Add(pnt);
                            tempNet[i, j].ClusterNum = leftCellCluster;
                        }
                    }
                }
            }

            HKResultNet resultNet = new HKResultNet(net.getWidth(), net.getHeight());
            for (int i=0; i<resultNet.getWidth(); ++i)
            {
                for (int j=0; j<resultNet.getHeight(); ++j)
                    resultNet.Net[i, j] = tempNet[i + 1, j + 1].ClusterNum;
            }

            return new HKStatistics(resultNet, dict);
        }
    }
}
